package com.c2b.algorithm.leetcode.lcr;

/**
 * <a href='https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/'>循环有序列表的插入</a>
 * <p>给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。</p>
 * <p>给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。</p>
 * <p>如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。</p>
 * <p>如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。</p>
 *
 * <p>
 * <b>示例:</b>
 * <pre>
 *  <a href='https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/'>查看示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>0 <= Number of Nodes <= 5 * 10^4</li>
 *     <li>-10^6 <= Node.val <= 10^6</li>
 *     <li>-10^6 <= insertVal <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/20 11:48
 */
public class LCR029 {
    static class Solution {
        public Node insert(Node head, int insertVal) {
            Node newNode = new Node(insertVal);
            if (head == null) {
                newNode.next = newNode;
                return newNode;
            }
            // 只有一个节点
            if (head.next == head) {
                head.next = newNode;
                newNode.next = head;
                return head;
            }
            Node currNode = head;
            Node nextNode = currNode.next;
            while (nextNode != head) {
                // 如果在递增的一段链表中
                if (insertVal >= currNode.val && insertVal <= nextNode.val) {
                    break;
                }
                // 如果在递减的节点。由最大值来到最小值的节点
                if (currNode.val > nextNode.val) {
                    if (insertVal >= currNode.val || insertVal <= nextNode.val) {
                        break;
                    }
                }
                currNode = currNode.next;
                nextNode = nextNode.next;
            }
            currNode.next = newNode;
            newNode.next = nextNode;
            return head;
        }
    }

    static class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }
}
